package com.epam.rd.myCollections.list;

import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class MyLinkedList implements MyList {
	private static class Node {
		Object item;
		Node next;
		Node prev;

		Node(Node prev, Object element, Node next) {
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
	}

	private int size = 0;
	private Node first;
	private Node last;

	public MyLinkedList() {
	}

	public void add(int index, Object element) {

		if (index == size)
			linkLast(element);
		else {
			checkIndex(index);
			linkBefore(element, node(index));
		}
	}

	private void linkBefore(Object e, Node succ) {
		// assert succ != null;
		final Node pred = succ.prev;
		final Node newNode = new Node(pred, e, succ);
		succ.prev = newNode;
		if (pred == null)
			first = newNode;
		else
			pred.next = newNode;
		size++;
	}

	public void add(Object e) {
		linkLast(e);
	}

	public void addAll(int index, Object[] a) {
		if (index != size) {
			checkIndex(index);
		}

		// Object[] a = c.toArray();
		int numNew = a.length;

		Node pred, succ;
		if (index == size) {
			succ = null;
			pred = last;
		} else {
			succ = node(index);
			pred = succ.prev;
		}

		for (Object o : a) {
			Node newNode = new Node(pred, o, null);
			if (pred == null)
				first = newNode;
			else
				pred.next = newNode;
			pred = newNode;
		}

		if (succ == null) {
			last = pred;
		} else {
			pred.next = succ;
			succ.prev = pred;
		}

		size += numNew;
	}

	public void addAll(Object[] c) {
		addAll(size, c);
	}

	private void checkIndex(int index) {
		if (index < 0 || index >= size()) {
			throw new MyIndexOutOfBoundsException();
		}
	}

	public void clear() {
		for (Node x = first; x != null;) {
			Node next = x.next;
			x.item = null;
			x.next = null;
			x.prev = null;
			x = next;
		}
		first = last = null;
		size = 0;
	}

	public Object get(int index) {
		checkIndex(index);
		Node tempNode = first;
		for (int i = 1; i <= index; i++) {
			tempNode = tempNode.next;
		}
		return tempNode.item;
	}

	public Object getFirst() {
		final Node firstNode = first;
		if (firstNode == null) {
			throw new NoSuchElementException();
		}
		return first.item;
	}

	public Object getLast() {
		final Node lastNode = last;
		if (lastNode == null) {
			throw new NoSuchElementException();
		}
		return last.item;
	}

	public int indexOf(Object o) {
		int index = 0;
		if (o == null) {
			for (Node x = first; x != null; x = x.next) {
				if (x.item == null)
					return index;
				index++;
			}
		} else {
			for (Node x = first; x != null; x = x.next) {
				if (o.equals(x.item))
					return index;
				index++;
			}
		}
		return -1;
	}

	public boolean isEmpty() {
		return this.size() == 0;
	}

	void linkLast(Object e) {
		final Node l = last;
		final Node newNode = new Node(l, e, null);
		last = newNode;
		if (l == null)
			first = newNode;
		else
			l.next = newNode;
		size++;
	}

	private Node node(int index) {
		if (index < (size >> 1)) {
			Node x = first;
			for (int i = 0; i < index; i++)
				x = x.next;
			return x;
		} else {
			Node x = last;
			for (int i = size - 1; i > index; i--)
				x = x.prev;
			return x;
		}
	}

	public void remove(int index) {
		checkIndex(index);
		unlink(node(index));
	}

	public Object removeFirst() {
		final Node f = first;
		if (f == null)
			throw new NoSuchElementException();
		return unlinkFirst(f);
	}

	public Object removeLast() {
		final Node l = last;
		if (l == null)
			throw new NoSuchElementException();
		return unlinkLast(l);
	}

	public void set(int index, Object e) {
		checkIndex(index);
		Node x = node(index);
		Object oldVal = x.item;
		x.item = e;

	}

	public int size() {
		return size;
	}

	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for (Node x = first; x != null; x = x.next)
			result[i++] = x.item;
		return result;
	}

	private void unlink(Node node) {
		Object item = node.item;
		Node pr = node.prev;
		Node ne = node.next;

		if (pr != null) {
			pr.next = ne;
		} else {
			if (ne != null)
				ne.prev = null;
		}

		if (ne != null) {
			if (pr != null)
				pr.next = ne;
		} else {
			if (pr != null)
				pr.next = null;
		}

		item = null;
		size--;
	}

	private Object unlinkFirst(Node f) {
		final Object element = f.item;
		final Node next = f.next;
		f.item = null;
		f.next = null; // help GC
		first = next;
		if (next == null)
			last = null;
		else
			next.prev = null;
		size--;
		// modCount++;
		return element;
	}

	private Object unlinkLast(Node f) {
		final Object element = f.item;
		final Node prev = f.prev;
		f.item = null;
		f.prev = null; // help GC
		last = prev;
		if (prev == null)
			first = null;
		else
			prev.next = null;
		size--;
		// modCount++;
		return element;
	}

	public Iterator iterator() {
		return new ListItr();
	}

	private class ListItr implements Iterator {
		private Node lastReturned;
		private Node next = first;

		public Object next() {
			if (!hasNext())
				throw new NoSuchElementException();

			lastReturned = next;
			next = next.next;
			return lastReturned.item;
		}

		public void remove() {
			throw new NoSuchElementException();
		}

		public boolean hasNext() {
			if (next != null) {
				return true;
			}
			return false;
		}
	}

	public void addFirst(Object e) {
		final Node f = first;
		final Node newNode = new Node(null, e, f);
		first = newNode;
		if (f == null)
			last = newNode;
		else
			f.prev = newNode;
		size++;
	}

	public void addLast(Object e) {
		final Node l = last;
		final Node newNode = new Node(l, e, null);
		last = newNode;
		if (l == null)
			first = newNode;
		else
			l.next = newNode;
		size++;
	}

}
